This invention relates to the field of image/video processing, and in particular to determining motion vectors that are each assigned to individual image regions.
In image processing, a known approach is to assign motion vectors to individual image regions of an image, which is part of a sequence of images. The motion vectors each indicate a displacement of the position of this image region relative to a position for this image region in a previous or subsequent image of the image sequence. The motion information is useful, for example, in generating one or more intermediate images lying temporally between the images of the image sequence in order to correctly display the positions of moving objects in the intermediate images (i.e., displaying them with correct motion). The motion information for an object moving over multiple successive images may also be employed for the compressed storage of image data for successive images. In addition, the motion information for a moving object can also be utilized for an interline interpolation.
Motion vectors can also be assigned to image blocks of an intermediate image to be interpolated. The motion vector of an image block of an intermediate image in this case indicates from which image position in the previous image the content of this image block moves to which image position in the subsequent image.
One technique for generating motion vectors is the so-called block matching method which is described, for example, in Schröder, H.; Blume, H.: “Multidimensional Signal Processing”, Volume 2, ISBN 3-519-06197-X, pages 259-266. In this processing technique, the current image from an image sequence is subdivided into a number of blocks of equal size. For each of these blocks, a block whose content has the best match with the specific block of the current image is sought in the previous or subsequent image. The displacement vector between this block from the current image and the block from the previous or subsequent image which has the greatest number of matches with this block of the current image then forms the motion vector for the block of the current image. An estimation technique of this type for determining motion vectors is explained below based on FIG. 1. FIG. 1 illustrates an image sequence comprising a first image P(k−½) and a second image P(k+½) which follow each other either temporally or spatially, and comprising an intermediate image P(k) to be interpolated lying temporally or spatially between the first and second images.
Referring to FIG. 1, to implement motion estimation, the first image P(k−½) is subdivided into a number of image blocks using an image grid, indicated by the broken line. One such image block is identified in FIG. 1 by reference number 51. Each of these image blocks comprises a pixel matrix with a number of pixels, such as for example 4×8 pixels. Using an appropriate search algorithm, for each block of the first image Pk(k−½) the image block of the same size in the second image Pk(k+½) is determined that has the greatest number of matches with the respective image block of the first image. In FIG. 1, reference number 52 identifies one such image block image in the second image P(k+½) corresponding to the image block 51 of the first image.
This search for the corresponding image block 52 within the second image is not necessarily tied to the image grid, with the result that the position of the corresponding image block may lie outside the block grid specified for the first image P(k−½). The search for the corresponding image block in the second image can be effected with a resolution of one pixel.
For purposes of interpolation, the intermediate image to be interpolated is also subdivided, using a block grid that can correspond to the block grid of the first image P(k−½), into a number of image blocks to which one motion vector each is assigned. Reference notation 154 in FIG. 1 identifies one such image block. A motion vector V154 is assigned to the image block 154. The image content of the image block 154 can be interpolated using the motion vector by first determining the image block located in the first image P(k−½) at the position of the starting point of the motion vector V154 and by determining the image block in the second image P(k+½) that is located at the position of the end point of the motion vector V154. The image content of the image block 154 of the intermediate image P(k) to be interpolated can then be interpolated using the image information of these image blocks from the first and second images P(k−½), P(k+½).
The temporal or spatial position of the intermediate image P(k) between the first and second image must be taken into account in the assignment of motion vectors to the individual image blocks 154. For example, effect this assignment of motion vectors to image blocks of the intermediate image, the motion vectors V51 determined for the individual image blocks of the first image P(k−½) are projected into the intermediate image, and for each of these motion vectors V51 one pixel 53 lying on the motion vector V51 is determined. The local position of which between the starting point and end point of the motion vector V51 corresponds to the temporal or local position of the intermediate image P(k) between first and second images P(k−½), P(k+½). If the intermediate image P(k), for example, lies temporally midway between the first and second images P(k−½), P(k+½), then that pixel is determined which lies in the center of the motion vector, as shown in FIG. 1. The motion vector V51 is then assigned as the motion vector V154 to the image block 154 in which the determined pixel 53 lies. In FIG. 1, the motion vector V154 is shown as motion vector V154 proceeding through the midpoint of the image block.
In the motion estimation technique based on the full search algorithm, each block of the current image is compared with each block of the previous or subsequent image to determine the motion vectors of the individual regions. To reduce the considerable computational effort required for the full search algorithm, additional predictive estimation techniques are known in which motion information from prior motion estimates is utilized when determining the motion vector for a specific block.
With optimized search techniques, only a certain number of selection vectors or candidate vectors are assigned to each block. When using these selection vectors or candidate vectors, an image comparison is performed to select one of these vectors based on the comparison result, and to assign it to the block. Methods of this type are described in Schröder, H.; Blume, H.: “Multidimensional Signal Processing” [Mehrdimensionale Signalverarbeitung], Volume 2, ISBN 3-519-06197-X, pages 266-289. Another optimized search method using candidate vectors is described, for example, in U.S. Pat. No. 6,782,054.
The quality of the motion estimate using the block estimation technique is significantly dependent on the block resolution, that is, the size of the individual blocks. For example the quality increases as the size of the individual blocks decreases, in other words, as the resolution of the image in the individual blocks improves, and thus more motion vectors per image are determined. However, at the same time, the computational effort also increases with smaller block sizes. The susceptibility to errors also increases with decreasing block sizes. The optimum block size is thus approximately 4×8 (lines×pixels). However, with blocks of this size noticeable block structures are created during image processing. For example, when a round object moves in the image in front of a background, the block estimation can result in noticeable edges at the boundary of the object relative to the background.
One approach to increasing the resolution for the determination of motion vectors is known from U.S. Pat. No. 5,148,269, whereby the image is subdivided into a predetermined number of main blocks and a block estimate is first implemented to assign a motion vector to each of these main blocks. Each of the individual main blocks is then subdivided into a number of sub-blocks to which one motion vector each is assigned. The motion vector of the associated main block, and motion vectors of additional main blocks adjacent to the main block, are utilized to generate the motion vectors of the sub-blocks.
Another problem in the determination of motion vectors is that a motion vector can be assigned only to those image regions or objects that are actually present in successive images. Consider the case of an image sequence with an object that moves toward a boundary of the image sequence and is present in the first image of the image sequence, but is no longer present in a temporally following image. A motion estimation approach using a block estimation method in this case leads with a high degree of probability to an error. An analogous situation applies whenever an image sequence displays moving objects that are temporarily obscured by other objects in the image sequence.
Motion estimation is especially difficult whenever the image sequence has objects moving in opposite directions that obscure each other temporarily.
There is a need for an improved technique for determining motion vectors that are assigned to individual image regions of an image to be interpolated.